package com.gaofeng.algo.kt

import java.util.*

fun climbStairs(n: Int): Int {
    if (n < 3) {
        return n
    }
    var first = 1
    var second = 2
    var result = 0
    for (i in 3..n) {
        result = first + second
        first = second
        second = result
    }
    return result
}

fun rob(nums: IntArray): Int {
    if (nums.isEmpty()) {
        return 0
    }
    val size = nums.size
    if (size == 1) {
        return nums[0]
    }
    var first = 0
    var second = 0
    var current = 0
    for (i in 0 until size) {
        current = Math.max(second, first + nums[i])
        first = second
        second = current
    }
    return current
}

fun numberOfArithmeticSlices(A: IntArray): Int {
    if (A.size < 3) {
        return 0
    }
    var dp = IntArray(A.size)
    var sum = 0
    for (i in 2 until A.size) {
        if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
            dp[i] = dp[i - 1] + 1
            sum += dp[i]
        }
    }
    return sum
}

fun minPathSum(grid: Array<IntArray>): Int {
    if (grid.isEmpty()) {
        return 0
    }
    val m = grid.size
    val n: Int = grid[0].size
    val dp = Array(m) { IntArray(n) }
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (i == 0 && j == 0) {
                dp[i][j] = grid[i][j]
            } else if (i == 0) {
                dp[i][j] = dp[i][j - 1] + grid[i][j]
            } else if (j == 0) {
                dp[i][j] = dp[i - 1][j] + grid[i][j]
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
            }
        }
    }
    return dp[m - 1][n - 1]
}

fun minPathSum2(grid: Array<IntArray>): Int {
    if (grid.isEmpty()) {
        return 0
    }
    val m = grid.size
    val n: Int = grid[0].size
    val dp = IntArray(n)
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (i == 0 && j == 0) {
                dp[j] = grid[i][j]
            } else if (i == 0) {
                dp[j] = dp[j - 1] + grid[i][j]
            } else if (j == 0) {
                dp[j] = dp[j] + grid[i][j]
            } else {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j]
            }
        }
    }
    return dp[n - 1]
}

fun updateMatrix(matrix: Array<IntArray>): Array<IntArray>? {
    if (matrix.isEmpty()) {
        //创建一个空的二维数组,其实可以表示所有的空的数组
        return arrayOf()
    }
    val m = matrix.size
    val n: Int = matrix[0].size
    //创建一个空数据的二维int的数组
    val dp = Array(m) { IntArray(n) }
    for (i in 0 until m) {
        //给二维数组填充默认的值
        Arrays.fill(dp[i], Int.MAX_VALUE / 2)
    }
    for (i in 0 until m) {
        for (j in 0 until n) {
            //从左往右 然后向下移动
            if (matrix[i][j] == 0) {
                dp[i][j] = 0
            } else {
                if (i > 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1)
                }
                if (j > 0) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1)
                }
            }
        }
    }
    //从右向左,往上移动
    for (i in m - 1 downTo 0) {
        for (j in n - 1 downTo 0) {
            if (matrix[i][j] == 0) {
                dp[i][j] = 0
            } else {
                if (i < m - 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1)
                }
                if (j < n - 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1)
                }
            }
        }
    }
    return dp
}

fun numDecodings(s: String): Int {
    val size = s.length
    if (size == 0) {
        return 0
    }
    val dp = IntArray(size)
    if (s[0] == '0') {
        return 0
    }
    dp[0] = 1
    for (i in 1 until size) {
        if (s[i] != '0') {
            dp[i] = dp[i - 1]
        }
        val number = 10 * (s[i - 1] - '0') + (s[i] - '0')
        if (number in 10..26) {
            if (i == 1) {
                dp[i]++
            } else {
                dp[i] += dp[i - 2]
            }
        }
    }
    return dp[size - 1]
}


fun maximalSquare(matrix: Array<CharArray>): Int {
    val m = matrix.size
    if (m == 0) {
        return 0
    }
    val n = matrix[0].size
    val dp = Array(m) { IntArray(n) }
    var slide = 0
    for (i in 0..m) {
        for (j in 0..n) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1
                } else {
                    dp[i][j] = dp[i][j - 1].coerceAtLeast(dp[i - 1][j - 1].coerceAtLeast(dp[i - 1][j])) + 1
                }
                slide = slide.coerceAtLeast(dp[i][j])
            }
        }
    }
    return slide * slide
}

fun numSquares(n: Int): Int {
    val dp = IntArray(n + 1)
    Arrays.fill(dp, Int.MAX_VALUE)
    dp[0] = 0
    for (i in 1..n) {
        var j = 1
        while (j * j <= i) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
            j++
        }
    }
    return dp[n]
}

fun wordBreak(s: String, wordDict: List<String>): Boolean {
    val n = s.length
    val dp = BooleanArray(n + 1)
    dp[0] = true
    for (i in 1..n) {
        for (word in wordDict) {
            val len = word.length
            if (i >= len && s.substring(i - len, i) == word) {
                dp[i] = dp[i] || dp[i - len]
            }
        }
    }
    return dp[n]
}